#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 100

// 定义图的存储结构
typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];
    int num_vertices;
    bool visited[MAX_VERTICES];
} Graph;

// 初始化图
void initGraph(Graph* graph, int num_vertices) {
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        graph->visited[i] = false;
        for (int j = 0; j < num_vertices; j++) {
            graph->vertices[i][j] = 0;
        }
    }
}

// 添加有向边
void addDirectedEdge(Graph* graph, int from, int to) {
    graph->vertices[from][to] = 1;
}

// 添加无向边
void addUndirectedEdge(Graph* graph, int from, int to) {
    graph->vertices[from][to] = 1;
    graph->vertices[to][from] = 1;
}

// DFS遍历
void dfs(Graph* graph, int vertex) {
    printf("%d ", vertex);
    graph->visited[vertex] = true;
    for (int i = 0; i < graph->num_vertices; i++) {
        if (graph->vertices[vertex][i] == 1 && !graph->visited[i]) {
            dfs(graph, i);
        }
    }
}

// BFS遍历
void bfs(Graph* graph, int vertex) {
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;

    printf("%d ", vertex);
    graph->visited[vertex] = true;
    queue[rear++] = vertex;

    while (front < rear) {
        int current_vertex = queue[front++];
        for (int i = 0; i < graph->num_vertices; i++) {
            if (graph->vertices[current_vertex][i] == 1 && !graph->visited[i]) {
                printf("%d ", i);
                graph->visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    Graph graph;// = (Graph*)malloc(sizeof(Graph));
    int num_vertices = 5;
    initGraph(&graph, num_vertices);

    // 添加有向边
    addDirectedEdge(&graph, 0, 1);
    addDirectedEdge(&graph, 0, 2);
    addDirectedEdge(&graph, 1, 2);
    addDirectedEdge(&graph, 2, 0);
    addDirectedEdge(&graph, 2, 3);
    addDirectedEdge(&graph, 3, 3);

    //并使用2作为起始顶点进行DFS遍历和BFS遍历
    printf("DFS遍历:  ");
    dfs(&graph, 2);
    printf("\n");

    // 重置visited数组
    for (int i = 0; i < num_vertices; i++) {
        graph.visited[i] = false;
    }

    printf("BFS遍历: ");
    bfs(&graph, 2);
    printf("\n");

    return 0;
}
